\section{Results and Conclusion} Our objective with this project was to 
implement an algorithmic solution to solve a large scheduling problem with custom constraints. 

We started by approaching the problem thought a Linear Programming solution but found it 
infeasible due to the large number of variables needed for the modelling. This 
motivated us for the implementation of local search. Comparing local 
search with brute force, showed us the benefits of using local search 
according to both memory and run time. So the concluding remark is a 
recommendation of local search for scheduling problems. 

In developing the solution, we experimented with several concrete implementations of
local search. 

\subsection{Neighborhood} In our neighbor generation, we focused on a 
simple concept. Moving a single type of shift between departments on a 
given day. The chosen type of shift is summed for every department and 
correspondingly utilizing the $multiplier$, and in this fashion we can 
take from one set of departments and give to another. With this we 
experimented with the following solutions: 

\begin{itemize} \item Moving the total amount of shifts to the poorest 
department. \item Moving the total amount of shifts to the two poorest 
department. \item Moving the total amount of shifts to the all 
department from poor to rich in the given allocation; 1/2, 1/3 ... 
1/n-1, 1/n. \item Moving the richest departments shifts to the poorest 
department. \item Moving shifts from a random department to one or two 
other departments, depending on the capacity limits. \end{itemize} 

We choose the last solution for our project, based on our intuition 
about the structure of the specific scheduling problem. The added smart 
feature (Capacity limit checker), optimized the results even further. 
This gave us an understanding of how to utilize local search and the 
heuristics involved. 

\subsection{Cost functions} Modelling the cost function is, like 
modelling the neighbor function, the heuristics of local search. Since 
weighting the different cost functions is inherent in defining the 
problem for local search, this has been a matter of estimation according 
to the specific application. 

\subsection{Further work} \subsubsection{Linear programming} As 
mentioned previously, modelling the problem in linear programming, 
proved to beyond the scope of this project. Further work on this project 
could be centered around this assignment. \subsubsection{Dynamic 
programming}Modelling the project as a dynamic programming solution 
could be another way of dealing with our problem. Specifically the 
weighted interval scheduling problem could be of inspiration, in regards 
to our problem. Our problem, however, is not simply a problem of weighted
interval scheduling.
